package com.learn.dp;

/**
 * 给定一个数组，数组中的元素都是正数，且不重复的硬币面值，求解得到指定金额的方法数
 */
public class Money {

    public int getFun(int[] arr, int money) {
        return process(arr, 0, money);
    }


    /**
     * 在index位置，组成res金额的方法数
     *
     * @param arr
     * @param index
     * @param res   剩余需要达到的钱数
     * @return
     */
    public int process(int[] arr, int index, int res) {
        if (index == arr.length) {
            //剩余金额为0，达标
            return res == 0 ? 1 : 0;
        }

        int ways = 0;
        for (int zhang = 0; arr[index] * zhang <= res; zhang++) {
            ways += process(arr, index + 1, res - arr[index] * zhang);
        }
        return ways;

    }


    public int dp(int[] arr, int aim) {
        int N = arr.length;
        int[][] dpArr = new int[N + 1][aim + 1];

        dpArr[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                //方法1
//                int ways = 0;
//                for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
//                    ways += dpArr[index + 1][rest - arr[index] * zhang];
//                }
//                dpArr[index][rest] = ways;

                //优化,index,rest位置依赖下一行值，
                dpArr[index][rest] = dpArr[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dpArr[index][rest] += dpArr[index][rest - arr[index]];
                }
            }
        }

        return dpArr[0][aim];


    }
}
